/**
 * 
 */
package linkedlist.passed;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author xyyi
 *
 */
public class MergeSortedLinkedListsInPlace {

	/**
	 * Definition for singly-linked list.
	 */
	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}
	}

	class ListNodeComparator implements Comparator<ListNode> {

		@Override
		public int compare(ListNode o1, ListNode o2) {
			Integer value1 = o1.val;
			Integer value2 = o2.val;
			if (value1 == null) {
				return value2 == null ? 0 : 1;
			}
			if (value2 == null) {
				return value1 == null ? 0 : -1;
			}

			return value1.compareTo(value2);
		}
	}

	public ListNode mergeKLists(ArrayList<ListNode> lists) {
		// Start typing your Java solution below
		// DO NOT write main() function
		if (lists == null || lists.isEmpty())
			return null;

		PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(lists.size(),
				new ListNodeComparator());
		for (ListNode node : lists) {
			if (node != null)
				pq.offer(node);
		}

		ListNode dummyNode = new ListNode(-1);
		ListNode lastNode = dummyNode;
		while (!pq.isEmpty()) {
			ListNode minNode = pq.poll();
			if (minNode.next != null)
				pq.offer(minNode.next);
			lastNode.next = minNode;
			lastNode = lastNode.next;
		}

		return dummyNode.next;
	}

	/**
	 * 
	 */
	public MergeSortedLinkedListsInPlace() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
